package ee.homework.sixth;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class UniversalHashing {

	private List<Long> keys;
	private List<Integer> counters;
	private int minCounter = 10000000;
	private List<Long> items = new ArrayList<Long>(3);

	public static void main(String[] args) {
		UniversalHashing uh = new UniversalHashing();
		uh.counters = new ArrayList<Integer>();
		uh.readKeys();
		int iterations = 100;
		for (int i = 0; i < iterations; i++) {
			uh.run();
		}
		int sum = 0;
		for (Integer counter : uh.counters) {
			sum += counter;
		}
		System.out.println("Average trials count: " + sum / iterations);
		System.out.println("Minimum trials count: " + uh.minCounter);
		System.out.println("a: " + uh.items.get(0) + ", b: " + uh.items.get(1)
				+ ", p: " + uh.items.get(2));
	}

	private void run() {
		long M = Collections.max(keys);
		long p = M + 1;
		int size = 800;
		while (!isPrime(p)) {
			p = (int) (Math.random() * (M - 1) + (M + 1));
		}
		int counter = 0;
		boolean success = false;
		long a = 0;
		long b = 0;
		while (!success) {
			counter++;
			a = (long) (Math.random() * (p - 1) + 1);
			b = (long) (Math.random() * p);
			success = collisions(a, b, p, size);
		}
		if (counter < minCounter) {
			minCounter = counter;
			if (items.size() == 0) {
				items.add(a);
				items.add(b);
				items.add(p);
			} else {
				items.set(0, a);
				items.set(1, b);
				items.set(2, p);
			}
		}
		counters.add(counter);
	}

	private boolean collisions(long a, long b, long p, int size) {
		List<Long> tmp = new ArrayList<Long>();
		Long h;
		for (Long integer : keys) {
			h = universalHash(a, integer, b, p, size);
			if (!tmp.contains(h)) {
				tmp.add(h);
			} else {

			}
		}
		return keys.size() == tmp.size();

	}

	private long universalHash(long a, long k, long b, long p, int size) {
		return ((a * k + b) % p) % size;
	}

	private boolean isPrime(long number) {
		if (number <= 1) {
			return false;
		}
		if (number == 2) {
			return true;
		}
		for (int i = 2; i <= Math.sqrt(number) + 1; i++) {
			if (number % i == 0) {
				return false;
			}
		}
		return true;
	}

	private void readKeys() {
		try {
			BufferedReader reader = new BufferedReader(new FileReader(new File(
					"data\\keys.txt")));
			String line = null;
			keys = new ArrayList<Long>();
			while ((line = reader.readLine()) != null) {
				keys.add(Long.parseLong(line.trim()));
			}
		} catch (IOException e) {
			System.out.println("Error occurred while trying to read file: "
					+ e.getMessage());
		}
	}
}
